0678. 有效的括号字符串【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 贪心

1. 📝 题目描述

• leetcode

给你一个只包含三种字符的字符串，支持的字符类型分别是 '('、')' 和 '*'。请你检验这个字符串是否为有效字符串，如果是 有效 字符串返回 true。

有效 字符串符合如下规则：

• 任何左括号 '(' 必须有相应的右括号 ')'。
• 任何右括号 ')' 必须有相应的左括号 '('。
• 左括号 '(' 必须在对应的右括号之前 ')'。
• '*' 可以被视为单个右括号 ')'，或单个左括号 '('，或一个空字符串 ""。

---

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "(*)"
输出：true

示例 3：

输入：s = "(*))"
输出：true

---

提示：

• 1 <= s.length <= 100
• s[i] 为 '('、')' 或 '*'

2. 🎯 s.1 - 贪心

c

bool checkValidString(char* s) {
    int lo = 0, hi = 0;
    for (int i = 0; s[i]; i++) {
        if (s[i] == '(') { lo++; hi++; }
        else if (s[i] == ')') { lo--; hi--; }
        else { lo--; hi++; }
        if (hi < 0) return false;
        if (lo < 0) lo = 0;
    }
    return lo == 0;
}

js

/**
 * @param {string} s
 * @return {boolean}
 */
var checkValidString = function (s) {
  let lo = 0,
    hi = 0
  for (const c of s) {
    if (c === '(') {
      lo++
      hi++
    } else if (c === ')') {
      lo--
      hi--
    } else {
      lo--
      hi++
    }
    if (hi < 0) return false
    lo = Math.max(lo, 0)
  }
  return lo === 0
}

py

class Solution:
    def checkValidString(self, s: str) -> bool:
        lo = hi = 0
        for c in s:
            if c == '(':
                lo += 1; hi += 1
            elif c == ')':
                lo -= 1; hi -= 1
            else:
                lo -= 1; hi += 1
            if hi < 0:
                return False
            lo = max(lo, 0)
        return lo == 0

• 时间复杂度：$O(n)$，其中 n 是字符串长度
• 空间复杂度：$O(1)$

算法思路：

• 维护未匹配左括号数量的可能范围 [lo, hi]
• ( 使两者都 +1，) 都 -1，* 使lo -1、hi +1
• hi < 0 说明右括号多了，lo 不能小于 0，最终 lo == 0 则有效